#include <cstdio>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int r,l;
int P = 13331;
long long int mod = 1e9+7;
long long int p[2020];
char s[2020];
long long int hah[2020];
void gethah()
{
	hah[1] = s[1];
	for(int i = 2;i<2020;i++)
	{
		hah[i] = (hah[i-1]*P+s[i])%mod;
	}
}
int judge(int l,int r)
{
	map<int,int>mp;
	int len = 1;
	while(len<=r-l+1)
	{
		for(int i = l;i+len-1<=r;i++)
		{
			long long int temp;
			temp = hah[i+len-1]-(hah[i-1]*p[len])%mod;
		//	printf("+++%d %d",hash[i+len-1],hash[i-1]);
		//	printf("***%d\n",temp);
			mp[temp]++;
		}
		len++;
	}
	return mp.size();
}
int main()
{
	int t,ans;
	p[0]=1;
	for(int i = 1;i<2020;i++)
	{
		p[i] = p[i-1]*P;
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		gethah();
		int q;
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d %d",&l,&r);
		    ans = judge(l,r);
		    printf("%d\n",ans);
		}
	}
} 
